Search for: All records

Abstract Given a $$k$$-uniform hypergraph $$H$$ on $$n$$ vertices, an even cover in $$H$$ is a collection of hyperedges that touch each vertex an even number of times. Even covers are a generalization of cycles in graphs and are equivalent to linearly dependent subsets of a system of linear equations modulo $$2$$. As a result, they arise naturally in the context of well-studied questions in coding theory and refuting unsatisfiable $$k$$-SAT formulas. Analogous to the irregular Moore bound of Alon, Hoory, and Linial [3], Feige conjectured [8] an extremal trade-off between the number of hyperedges and the length of the smallest even cover in a $$k$$-uniform hypergraph. This conjecture was recently settled up to a multiplicative logarithmic factor in the number of hyperedges [12, 13]. These works introduce the new technique that relates hypergraph even covers to cycles in the associated Kikuchi graphs. Their analysis of these Kikuchi graphs, especially for odd $$k$$, is rather involved and relies on matrix concentration inequalities. In this work, we give a simple and purely combinatorial argument that recovers the best-known bound for Feige’s conjecture for even $$k$$. We also introduce a novel variant of a Kikuchi graph which together with this argument improves the logarithmic factor in the best-known bounds for odd $$k$$. As an application of our ideas, we also give a purely combinatorial proof of the improved lower bounds [4] on 3-query binary linear locally decodable codes. 

Let G be a random d-regular graph on n vertices. We prove that for every constant a>0, with high probability every eigenvector of the adjacency matrix of G with eigenvalue sufficiently small has Omega(n/polylog(n)) nodal domains.